#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//struct Interval{
//    int start;
//    int end;
//};
//
//bool compareInterval(Interval i1,Interval i2){
//    return (i1.start < i2.start);
//}

class Solution {
public:
    vector<vector<int> > merge(vector<vector<int> >& intervals) {
        // 计算二维数组的行数
        int n = intervals.size();
        // 如果只有一行则直接返回这个二维数组
        if(n==1) {
            return intervals;
        }
        // 对这个二维数组排序(每一行的第一个元素升序排序)

        sort(intervals.begin(), intervals.end());
        // 声明一个 新的二维数组(用来存放改变后的新数组)
        vector<vector<int>> vec;
        // 将二维数组的第一行放到新的二维数组中
        vec.push_back(intervals[0]);
        //	vec = {{1,3}}

        // 遍历二维数组每一行
        // 定义变量j是为了控制二维数组每一行的最后一个元素
        int j = 0;
        for(int i = j+1;i<n;i++){
            // 如果源数组第i(i=j+1)行第一个元素与新数组第j行最后一个元素做比较
            if(intervals[i][0]<=vec[j][1]) {
                //  intervals[1][0] <= vec[0][1]
                //                2 <= 3        true -> 76
                //  intervals[2][0] <= vec[0][1]
                //				  8 <= 6		false -> 83
                //  intervals[3][0] <= vec[1][1]
                //				 15 <= 10		false -> 83
                // 如果源数组第i(i=j+1)行第一个元素小于新数组第j行最后一个元素
                // 将新数组第j行最后一个元素与源数组第i行最后一个数组进行比较，将大的那一个值赋值给新数组的第j行最后一个元素
                vec[j][1] = max(vec[j][1], intervals[i][1]);
                //  vec[0][1] = max(3,6)
                //  vec[0][1] = 6
                //  vec = {{1,6}}
            } else{
                // 如果源数组第i(i=j+1)行第一个元素大于新数组第j行最后一个元素
                // 否则将源数组第i行数据添加到新数组
                vec.push_back(intervals[i]);
            //	vec = {{1,6},{8,10}}
            //	vec = {{1,6},{8,10},{15,18}}
                // j自增1，为了控制新的一行(i=j+1+1,j=j+1)
                j++;
            }
        }
        // 循环结束返回已经修改好的新数组
        return vec;
    }
};

int main(){
    // 声明一个可变二维数组(向量)
    vector<vector<int> > intervals = {{1,3},{2,6},{8,10},{15,18}};
    Solution s;

    for (int i = 0; i < s.merge(intervals).size(); i++) {
        for (int j = 0; j < s.merge(intervals)[i].size(); j++) {
            cout << s.merge(intervals)[i][j] << "\t";
        }
        cout << endl;
    }

//    Interval arr[] = {{6,8},
//                      {1,9},
//                      {3,5},
//                      {2,4}};
//    int n = sizeof (arr) / sizeof (arr[0]);
//
//    sort(arr,arr+n, compareInterval);
//
//    for (int i = 0; i < n; i++) {
//        cout << "[" << arr[i].start << "," << arr[i].end << "]" << endl;
//    }
}